package 删除二叉搜索树中的节点;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 删除二叉搜索树中的节点
 * @date 2022/11/8 12:06
 */
public class Demo450 {


    //Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
          root=delete(root,key);
          return root;
    }
    //递归三部曲
    private TreeNode delete(TreeNode root, int key) {
        //根节点为空，直接返回
        if(root==null) {
            return null;
        }
        if(root.val>key){
            //开始递归
            root.left=deleteNode(root.left,key);
        }else if(root.val<key){
            //开始递归
            root.right=deleteNode(root.right,key);
        }else {
            //返回条件。左子树为空，返回右子树
            if(root.left==null){
                return root.right;
            //返回条件。右子树为空，返回左子树
            }else if(root.right==null){
                return root.left;
            }else {
                //左右子树都不为空，找到右子树最小的，将左子树赋值给右子树最小的节点的左子树
                TreeNode tempPre = root.right;
                TreeNode temp=root.right.left;
                while (temp!=null){
                    tempPre=temp;
                    temp=temp.left;
                }
                tempPre.left=root.left;
                return root.right;
            }
        }
        return root;
    }

}
